package _107BinaryTreeLevelOrderTraversalTwo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CSolution {

  public static void main(String[] args) {
    System.out.println("aa");
    CSolution cSolution = new CSolution();
    TreeNode t1 = new TreeNode(3);
    TreeNode t2 = new TreeNode(9);
    TreeNode t3 = new TreeNode(20);
    TreeNode t4 = new TreeNode(15);
    TreeNode t5 = new TreeNode(7);
    t1.left = t2;
    t1.right = t3;
//    t3.left = t4;
//    t3.right = t5;
    cSolution.levelOrderBottom(t1);
  }

  private List<List<Integer>> levelOrderBottom(TreeNode root) {
    ArrayList<List<Integer>> result = new ArrayList<>();
    if (root == null) {
      return result;
    }
    List<TreeNode> nodeList = new ArrayList<>();
    List<TreeNode> nextNodeList = new ArrayList<>();
    nodeList.add(root);
    while (nodeList.size() != 0 || nextNodeList.size() != 0) {
      List<Integer> values = new ArrayList<>();
      for (int i = 0; i < nodeList.size(); i++) {
        values.add(nodeList.get(i).val);
        if (nodeList.get(i).left != null) {
          nextNodeList.add(nodeList.get(i).left);
        }
        if (nodeList.get(i).right != null) {
          nextNodeList.add(nodeList.get(i).right);
        }
      }
      result.add(values);
      nodeList = nextNodeList;
      nextNodeList = new ArrayList<>();
    }
    Collections.reverse(result);
    return result;
  }
}
